o_Comp-Prog 典型90問を解く(01~10)〔進行中〕 - luckYrat

o_Comp-Prog 典型90問を解く(01~10)〔進行中〕

タイトル通りです

こっちは飛ばす問題なさそうですが、理解するために解説する問題でない場合は軽いコメントだけ書きます

ちなみに解説ACの場合はその旨を書きます

解説があるので閲覧には注意してください

残り問題

3(類題),

4(類題),

5(★7),

6(類題),

8(類題),

9(★6)

解説と提出

1(AC, 類題AC)

これ二分探索か

類題

ABC023-D(射撃王) : AC

さっぱりわかりませんが

普通にありました Submission

s8pc#5-B(Emblem) :AC

確かに二分探索見えますね(未実装)

実装重いなーって思ったら全然そんなことなかった Submission

std::setを使いながら枝刈り全探索を行えば解ける

いやbit全探索は気付かんでしょ

類題

ABC190-C(Bowls and Dishes) : AC

全部の条件を満たす通り数と勘違いしていたが、まあ普通に虚無

ABC197-C(ORXOR) : 既AC

ABC064-D(Insertion) : 既AC

木の直径ですね

非本質で死んでた、一生見つかんなかった気がする

ライブラリ化をしたのがこちらになります

類題

ABC014-D(閉路(30点解法))

ABC019-D(高橋くんと木の直径) : 既AC

類題β(自前用意)

Yosupo_Judge-TreeDiameter(Link) : AC

ライブラリ化しました g_木の直径参照

AOJ-GRL-5-A(木の直径) : AC

ARC022-C(ロミオとジュリエット) : AC

まあ木の直径ライブラリ化しちゃったらやるだけになるわけで

AGC033-C(Removing Coins)

HとWに分ければ解ける(包除原理)

類題

ABC129-D(Lamp) : 既AC

え、これどうすればいいのって思ったらn+1個の要素が現れるのが本質っぽい？

一見だと余り持った桁DPぽいって思うけど(未実装)

10^18桁じゃん、ありがとう　ダブリングでもすればいいの？

SegmentTree使って範囲min取れば良いんですか…?

あーはいはい前処理配列用意すればセグ木いらないのね

類題

ABC076-C(Dubious Document 2) : 既AC

ABC009-C(辞書式順序ふたたび)

JOI2021-春合宿(Event Hopping 2)

二分探索というかstd::lower_boundを知っていますかのやつ

類題

AOJ-ALDS1-4-B(二分探索) : 既AC

ABC077-C(Snuke Festival) : 既AC

単純なDP了解！

類題

DDCC2019本選-D(DISCO!)

TL13秒...13秒!?

解説にはO(S|Q|)解法って書いてあるから多分TLE解だよね

ABC159-F(Knapsack for All Segments) : 既AC(だけどもう一度解く)

Submission-PAST

これマジで何？理解できないんだけど

みんなのプロコン2019-D(Ears)

あ、これが例の...

何もわかりません、O(N^2 logN)?

10(AC,類題AC)

累積和を知っています

類題

JOI2007-本選1(最大の和) : 既AC

JOI2010-本選1(旅人) : 既AC

ABC177-C(Sum of product of pairs) : 既AC

ABC182-D(Wandaring) : AC

リアルタイム累積和の典型例ですね(前処理することが多かったため新鮮)